﻿// 循环赛问题.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include <time.h>
#include <fstream>
using namespace std;

const int MAX_SIZE = 1000000;

int init(int& n, int& day);
int dcs_n(int** table, int n);
int dcs_solution(int** table, int n, int day);
int dcs_n(int** table, int n);
int dcs_day(int** table, int day);

int main()
{
	int n = 0, day = 0, ** table = NULL;// 数据规模、比赛天数、比赛表
	// ofstream outfile("output.txt");
	if (init(n, day) < 0) {
		cout << "输入不合法" << endl;
		exit(1);
	}
	table = (int**)malloc(sizeof(int*) * (day + 1));
	if (table == NULL) {
		cout << "内存分配失败" << endl;
		exit(1);
	}
	for (int i = 0; i < day + 1; i++) {
		table[i] = (int*)malloc(sizeof(int) * day);
		if (table[i] == NULL) {
			cout << "内存分配失败" << endl;
			exit(1);
		}
	}

	clock_t start, finish;
	double totaltime;
	start = clock();
	dcs_solution(table, n, day);
	finish = clock();
	totaltime = (double)(finish - start) / CLOCKS_PER_SEC;

	/*
	outfile << "run time:  " << totaltime << "s\n" << endl;
	for (int i1 = 0; i1 < n; i1++) {
		outfile << i1 + 1 << " : ";
		for (int i0 = 0; i0 < day; i0++)
			outfile << "\t" << table[i1][i0];
		outfile << endl;
	}
	outfile << endl;
	outfile.close();
	*/

	cout << "run time:  " << totaltime << "s\n" << endl;
	for (int i = 0; i < day + 1; i++)
		free(table[i]);
	free(table);
	return 0;
}

int init(int& n, int& day) {
	// 当n为奇数时，假设还有一个人存在（编号为n+1），当计算完后再将这个人去掉（编号改为0）
	cout << "输入比赛规模（小于100,000）：" << endl;
	cin >> n;
	if (n > MAX_SIZE)
		return -1;// n超过上限
	if (n <= 1)
		return -3;// n过小
	if ((n / 2) * 2 == n)
		day = n - 1;
	else day = n;
	return 0;
}

int dcs_solution(int** table, int n, int day) {
	if (n > 2) {
		int a = n - n / 2, b = a;
		if ((a / 2) * 2 == a)
			b--;
		dcs_solution(table, a, b);
	}
	dcs_n(table, day + 1);
	dcs_day(table, day);
	if (day == n)
		for (int i0 = 0; i0 < day; i0++)
			for (int i1 = 0; i1 < n; i1++)
				if (table[i1][i0] > n)
					table[i1][i0] = 0;
	return 0;
}

int dcs_n(int** table, int n) {
	// 这里虽然是n，但实际是假设的n
	if (n == 2) {
		table[0][0] = 2;
		table[1][0] = 1;
	}
	else {
		int pass_n = n / 2, pass_day = pass_n;
		if ((pass_day / 2) * 2 == pass_day)
			pass_day--;
		for (int i0 = 0; i0 < pass_day; i0++)
			for (int new_n = pass_n; new_n < n; new_n++) {
				int old_n = new_n - n / 2;
				if (table[old_n][i0] == 0) {
					table[old_n][i0] = new_n + 1;
					table[new_n][i0] = old_n + 1;
				}
				else {
					int a = table[old_n][i0] + n / 2;
					table[new_n][i0] = a;
				}
			}
	}
	return 0;
}

int dcs_day(int** table, int day) {
	if (day <= 1)
		return 0;
	int pass_n = (day + 1) / 2, pass_day = pass_n;
	if ((pass_day / 2) * 2 == pass_day)
		pass_day--;
	for (int i0 = pass_day; i0 < day; i0++) {
		for (int i1 = 0; i1 < pass_n; i1++) {
			int rvalue = (i0 - pass_day + i1 + 1) % pass_n + pass_n + 1;
			table[i1][i0] = rvalue;
			table[rvalue - 1][i0] = i1 + 1;
		}
	}
	return 0;
}